<!DOCTYPE html>
<html>
<head>
    <title>连连看</title>
    <meta name="keywords" content=""/>
    <meta name="description" content=""/>
    <meta charset="utf-8">
    <meta name="viewport" content="width=720, user-scalable=no"/>
    <meta name="author" content=""/>
    <meta name="copyright" content=""/>
    <meta name="viewport" content="width=device-width,initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no"/>
    <script src="https://cdn.staticfile.org/jquery/3.3.1/jquery.min.js"></script>
    <style>
        .activity {
            background-color: #009688;
            display: inline-block;
            border: 1px #fff solid;
            text-align: center;
            color: #fff;
            cursor: pointer;
        }
        .inActivity {
            background-color: #b6b4b6;
            display: inline-block;
            text-align: center;
            border: 1px #fff solid;
            cursor: pointer;
        }
        .run {
            background-color: #2196F3;
        }
        .start {
            background-color: #FF9800;
        }
        .end {
            background-color: #9C27B0;
        }
        .top{
            position: relative;
        }
        .create-btn{
            position: absolute;
            right: 0px;
            border-bottom: none;
            padding: 3px 25px;
            background: #FF5722;
            color: #fff;
            line-height: 40px;
            height: 40px;
            top: 0;

        }
        .width-input{
            width: 100%;
            height: 40px;
            font-size: 40px;
            text-align: center;
            background-color: #e0e4e4;
        }
        body{margin: 0}
        .do{
            border: 1px #009688 solid;
            padding: 10px 0px;
            width: 98%;
            display: inline-block;
            text-align: center;
            color: #009688;
        }

    </style>
</head>
<body>
<div class="top">
    <input class="width-input" id="width" placeholder="边长" value="6" />
    <!--<input type="button" id="makeContent" value="创建表格"/>-->
    <a class="create-btn" id="makeContent">创建表格</a>
</div>

<div id="content" style="width: 510px;height: 510px">

</div>
<div style="font-size: 15px">
    <div style="background-color:#009688;height: 20px;width: 20px;display: inline-block">&nbsp;</div>活动节点
    <div style="background-color:#b6b4b6;height: 20px;width: 20px;display: inline-block">&nbsp;</div>非活动节点
    <div style="background-color:#FF9800;height: 20px;width: 20px;display: inline-block">&nbsp;</div>开始节点
    <div style="background-color:#9C27B0;height: 20px;width: 20px;display: inline-block">&nbsp;</div>结束节点
    <div style="background-color:#2196F3;height: 20px;width: 20px;display: inline-block">&nbsp;</div>路径节点
</div>
<hr>
<div style="width: 100%;text-align: center">
    <a class="do" id="do">计算路径</a>
</div>
<div id="response">
</div>
</body>
</html>
<script>
    var maxRoute = "";
    /**
     * 生成表格
     * */
    $("#makeContent").click(function () {
        contentWidth = $(window).width();
        $("#content").css("width",($(window).width())+"px").css("height",($(window).width())+"px")


        $("#content").html("");
        width = $("#width").val();
        changkuan = contentWidth / width;
        for (i = 0; i < width; i++) {
            $tr = $("<div></div>").css("width", "100%").css("height", changkuan + "px")
            for (j = 0; j < width; j++) {
                $tr.append($("<span>" + i + "," + j + "</span>").css("width", (changkuan - 2) + "px").css("height", (changkuan - 2) + "px").addClass("activity").css("line-height", (changkuan - 2) + "px"))
            }
            $("#content").append($tr);
        }
        $("span").click(function () {
            //$(this).toggleClass("activity").toggleClass("inActivity");
            if (this.className =="activity") {
                this.className="inActivity";
            }
            else if(this.className=="inActivity"){
                this.className="start activity";
            }
            else if(this.className=="start activity"){
                this.className="end activity";
            }
            else if(this.className=="end activity"){
                this.className="activity";
            }
        }).dblclick(function () {
            /*if (this.className.indexOf("start") >= 0) {
                $("span").removeClass("end");
                $(this).removeClass("start").addClass("end")
                $(this).removeClass("inActivity").addClass("activity");
            }
            else if (this.className.indexOf("end") >= 0) {
                $("span").removeClass("end");
            }
            else {
                $("span").removeClass("start");
                $(this).addClass("start");
                $(this).removeClass("inActivity").addClass("activity");
            }*/
        });
    });

    $("#makeContent").click();

    var ex, ey, max, min;
    /**
     *  执行计算
     * */

    $("#do").click(function () {
        $(this).text("计算中，请稍候")
        setTimeout(function () {
            $("#response").html("");
            startTime = new Date();

            //遍历表格成素数组
            var array = [];
            var trs = $("#content>div");
            var spanArrays = [];
            $("#response").append("<p>遍历表格获取数组</p>");
            $.each(trs, function () {
                var trArray = [];
                var spanTr = [];
                $.each($(this).find("span"), function () {
                    trArray.push(this.className.indexOf("activity")>=0 ? 1 : 0);
                    spanTr.push(this);

                    //获取起始结束节点
                    if (this.className.indexOf("start") >= 0) {
                        sy=trArray.length-1;
                        sx=array.length;
                    }
                    else if (this.className.indexOf("end") >= 0) {
                        ey=trArray.length-1;
                        ex=array.length-1;
                    }

                })
                array.push(trArray);
                spanArrays.push(spanTr)
            })

            //计算

            // var array2 = [[0, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 0, 1, 1, 0], [0, 1, 1, 1, 1], [0, 1, 1, 1, 0]];
            max = array.length - 1;
            min = 0;
            //算法
            $("#response").append("<p>开始递归计算路径</p>");
            excute(sx, sy, JSON.parse(JSON.stringify(array)), "开始");
            $("#response").append("<p>计算完成</p>");
            console.log("最终："+maxRoute);
            //
            $("#response").append("<p>渲染结果</p>");

            var result = maxRoute.split("->");
            result.splice(0,1);
            result.splice(result.length-1,1);
            $.each(result,function(i,e){
                x=this.split(",")[0];
                y=this.split(",")[1];
                $(spanArrays[x][y]).addClass("run").text(i+1);
            })
            endTime = new Date();
            // console.log(array);
            $("#response").append("<p>完成！耗时"+(endTime.getTime()-startTime.getTime())/1000+"秒"+"</p>");

            $("#do").text("计算路径")
        },200)


    })


    /**
     * 递归执行
     * @param cx
     * @param cy
     * @param array
     * @param route
     * @returns {boolean}
     */
    function excute(cx, cy, array, route) {
        //设置已执行
        array[cx][cy] = 2;
        route += "->" + cx + "," + cy;
        //console.log(getEnabledChildNode(cx,cy,array));
        childNodeArray = getEnabledChildNode(cx,cy,array);
        //无出口节点，路径终止
        if (childNodeArray.length==0) {
            route += "->终止";
            //console.log(route);
            maxRoute = route.length>=maxRoute.length?route:maxRoute;
            return false;
        }
        else {
            //统计出口只有1的的节点数
            var nodeNumOfExitingNodeNumIsOne = 0;
            $.each(childNodeArray,function(){
               if(this.childNodeNum==1){
                   nodeNumOfExitingNodeNumIsOne++;
               }
            });
            //个数为1，就执行那个，其他剪枝
            if(nodeNumOfExitingNodeNumIsOne==1){
                $.each(childNodeArray,function(){
                    if(this.childNodeNum==1){
                        excute(this.x, this.y, JSON.parse(JSON.stringify(array)), route)
                    }
                });
            }
            else if(nodeNumOfExitingNodeNumIsOne==0){
                $.each(childNodeArray,function(){
                    excute(this.x, this.y, JSON.parse(JSON.stringify(array)), route)
                });
            }
            else
            {
                //多个单出口节点，说明不可用
            }
        }
    }

    /**
     * 获取有效的子节点
     * @param cx
     * @param cy
     * @param array
     */
    function getEnabledChildNode(cx, cy, array){
        var enabledChildNodeArray = [];
        if(cy + 1 <= max && array[cx][cy + 1] == 1){
            enabledChildNodeArray.push({x:cx,y:cy+1,childNodeNum:getEnabledChildNodeNum(cx, cy, JSON.parse(JSON.stringify(array)))});
        }
        if(cy - 1 >= min && array[cx][cy - 1] == 1){
            enabledChildNodeArray.push({x:cx,y:cy-1,childNodeNum:getEnabledChildNodeNum(cx, cy, JSON.parse(JSON.stringify(array)))});
        }
        if(cx + 1 <= max && array[cx+1][cy] == 1){
            enabledChildNodeArray.push({x:cx+1,y:cy,childNodeNum:getEnabledChildNodeNum(cx, cy, JSON.parse(JSON.stringify(array)))});
        }
        if(cx - 1 >= min && array[cx-1][cy] == 1){
            enabledChildNodeArray.push({x:cx-1,y:cy,childNodeNum:getEnabledChildNodeNum(cx, cy, JSON.parse(JSON.stringify(array)))});
        }
        return enabledChildNodeArray;
    }

    /**
     * 统计节点的出口数
     * @param cx
     * @param cy
     * @param array
     * @returns {number}
     */
    function getEnabledChildNodeNum(cx, cy, array){
        array[cx][cy]=2;
        num = 0;
        if(cy + 1 <= max && array[cx][cy + 1] == 1){
            num++;
        }
        if(cy - 1 >= min && array[cx][cy - 1] == 1){
            num++;
        }
        if(cx + 1 <= max && array[cx+1][cy] == 1){
            num++;
        }
        if(cx - 1 >= min && array[cx-1][cy] == 1){
            num++;
        }
        return num;

    }


</script>



